package com.zlk.algorithm.algorithm.recursion;

/**
 * @program: algorithm
 * @ClassName Hanoita
 * @description: 汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，
 * 源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上
 * 按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在
 * 另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只
 * 能移动一个圆盘。问应该如何操作？
 * @author: slfang
 * @create: 2024-03-25 10:40
 * @Version 1.0
 **/
public class Hanoita {

    public static void hanoi1(int n) {
        leftToRight(n);
    }

    // 请把1~N层圆盘 从左 -> 右
    public static void leftToRight(int n) {
        if (n == 1) { // base case
            System.out.println("Move 1 from left to right");
            return;
        }
        leftToMid(n - 1);
        System.out.println("Move " + n + " from left to right");
        midToRight(n - 1);
    }

    // 请把1~N层圆盘 从左 -> 中
    public static void leftToMid(int n) {
        if (n == 1) {
            System.out.println("Move 1 from left to mid");
            return;
        }
        leftToRight(n - 1);
        System.out.println("Move " + n + " from left to mid");
        rightToMid(n - 1);
    }

    public static void rightToMid(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightToLeft(n - 1);
        System.out.println("Move " + n + " from right to mid");
        leftToMid(n - 1);
    }

    public static void midToRight(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n - 1);
        System.out.println("Move " + n + " from mid to right");
        leftToRight(n - 1);
    }

    public static void midToLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n - 1);
        System.out.println("Move " + n + " from mid to left");
        rightToLeft(n - 1);
    }

    public static void rightToLeft(int n) {
        if (n == 1) {
            System.out.println("Move 1 from right to left");
            return;
        }
        rightToMid(n - 1);
        System.out.println("Move " + n + " from right to left");
        midToLeft(n - 1);
    }


    public static void main(String[] args) {
        int n = 3;
        //都可以抽像  因为任何时候，在小圆盘上都不能放大圆盘
       // hanoi1(n);
        System.out.println("============");
        hanoi2(n);
    }

    private static void hanoi2(int n) {
        if(n>0){
            func(n,"left","right","mid");
        }
    }

    //todo
    private static void func(int n,String from, String to, String depand) {
        if(n==1){
            System.out.println("Move 1 from " + from + " to " + to);
        }else{
            func(n-1,from,depand,to);
            System.out.println("Move " + n + " from " + from + " to " + to);
            func(n-1,depand,to,from);
        }
    }

}
